
/******************************************************************************
 *  A Teaching GA					  Developed by Hal Stringer & Annie Wu, UCF
 *  Version 2, January 18, 2004
 *******************************************************************************/
import java.io.*;
import java.util.*;

public class Search
{

   /*******************************************************************************
    *                           INSTANCE VARIABLES                                 *
    *******************************************************************************/
   /*******************************************************************************
    *                           STATIC VARIABLES                                   *
    *******************************************************************************/
   public static FitnessFunction problem;
   public static Chromo[] member;
   public static Chromo[] child;
   public static Chromo bestOfGenChromo;
   public static int bestOfGenR;
   public static int bestOfGenG;
   public static Chromo bestOfRunChromo;
   public static int bestOfRunR;
   public static int bestOfRunG;
   public static Chromo bestOverAllChromo[]; // GWM - Updated to array
   public static int BEST_CHROMO_COUNT = 10; // GWM - Set this to the number of best chromos to track
   public static int bestOverAllR;
   public static int bestOverAllG;
   public static double sumRawFitness;
   public static double sumRawFitness2;	// sum of squares of fitness
   public static double sumSclFitness;
   public static double sumProFitness;
   public static double defaultBest;
   public static double defaultWorst;
   public static double averageRawFitness;
   public static double stdevRawFitness;
   //CR
   public static double sumAvgRawFitness;
   public static double sumAvgRawFitness2;
   public static double stdevAvgAvgFitness;
   public static double stdevAvgBestFitness;
   public static int G;
   public static int R;
   public static Random r = new Random();
   private static double randnum;
   private static int memberIndex[];
   private static double memberFitness[];
   private static int TmemberIndex;
   private static double TmemberFitness;
   private static double fitnessStats[][];  // 0=Avg, 1=Best
   // CR - Added 2=Avg^2 3=Bes^t2
   // CR - array for all of the best of run chromos
   private static double bestOfRunsRawFitness[];
   private static Constant constant;

   //////////////////////////////////////////////////////////////////////////////
   // Test output to print the population.
//	public static PrintWriter popOutput;
   //////////////////////////////////////////////////////////////////////////////
   /*******************************************************************************
    *                              CONSTRUCTORS                                    *
    *******************************************************************************/
   /*******************************************************************************
    *                             MEMBER METHODS                                   *
    *******************************************************************************/
   /*******************************************************************************
    *                             STATIC METHODS                                   *
    *******************************************************************************/
   public static void main(String[] args) throws java.io.IOException
   {
      Calendar dateAndTime = Calendar.getInstance();
      Date startTime = dateAndTime.getTime();

      //  Read Parameter File
      System.out.println("\nParameter File Name is: " + args[0] + "\n");
      Parameters parmValues = new Parameters(args[0]);

      //  Write Parameters To Summary Output File
      String summaryFileName = Parameters.sumoOutputPath + Parameters.expID + "_summary.csv";
      FileWriter summaryOutput = new FileWriter(summaryFileName);
      Parameters.outputParameters(summaryOutput);


      //	Set up Fitness Statistics matrix
      // CR - from 2 to 4 to add new fitnessStats
      fitnessStats = new double[4][Parameters.generations];
      for (int i = 0; i < Parameters.generations; i++)
      {
         fitnessStats[0][i] = 0;
         fitnessStats[1][i] = 0;
         fitnessStats[2][i] = 0;
         fitnessStats[3][i] = 0;
      }

      // CR - init best of runs fitness array
      bestOfRunsRawFitness = new double[Parameters.numRuns];

      //	Problem Specific Setup - For new new fitness function problems, create
      //	the appropriate class file (extending FitnessFunction.java) and add
      //	an else_if block below to instantiate the problem.

      if (Parameters.problemType.equals("GA_TLP"))
      {
         problem = new GA_TLP();
      } else if (Parameters.problemType.equals("GA_TLP2"))
      {
         problem = new GA_TLP2();
      } else if (Parameters.problemType.equals("GA_TLP3"))
      {
         problem = new GA_TLP3();
      } else if (Parameters.problemType.equals("GA_TLP4"))
      {
          problem = new GA_TLP4();
      } 
      else
      {
         System.out.println("Invalid Problem Type");
      }

      System.out.println(problem.name);

      //	Initialize RNG, array sizes and other objects
      r.setSeed(Parameters.seed);
      memberIndex = new int[Parameters.popSize];
      memberFitness = new double[Parameters.popSize];

      member = new Chromo[Parameters.popSize];
      child = new Chromo[Parameters.popSize];
      bestOfGenChromo = new Chromo();
      bestOfRunChromo = new Chromo();


      if (Parameters.minORmax.equals("max"))
      {
         defaultBest = 0;
         defaultWorst = 999999999999999999999.0;
      } else
      {
         defaultBest = 999999999999999999999.0;
         defaultWorst = 0;
      }

      bestOverAllChromo = new Chromo[BEST_CHROMO_COUNT];
      for (int i = 0; i < BEST_CHROMO_COUNT; i++) // GWM - Updated to initialize each member of the array
      {
         bestOverAllChromo[i] = new Chromo();
         bestOverAllChromo[i].rawFitness = defaultBest;
      }

      //  Start program for multiple runs
      for (R = 1; R <= Parameters.numRuns; R++)
      {

         bestOfRunChromo.rawFitness = defaultBest;
         // CR - poor place for this, but just an initialization
         bestOfRunsRawFitness[R - 1] = defaultBest;
         //System.out.println();

         //	Initialize First Generation
         for (int i = 0; i < Parameters.popSize; i++)
         {
            member[i] = new Chromo();
            child[i] = new Chromo();
         }

         //Print headings
         summaryOutput.write("Run,Gen,Best,Avg,AvgStdDev,");
         PrintSumoStatHeaders(summaryOutput);

         System.out.println("Start of run: " + R);
         //	Begin Each Run
         for (G = 0; G < Parameters.generations; G++)
         {
            System.out.println("generation:" + G);
            sumProFitness = 0;
            sumSclFitness = 0;
            sumRawFitness = 0;
            sumRawFitness2 = 0;
            bestOfGenChromo.rawFitness = defaultBest;

            //	Test Fitness of Each Member
            for (int i = 0; i < Parameters.popSize; i++)
            {

               member[i].rawFitness = 0;
               member[i].sclFitness = 0;
               member[i].proFitness = 0;

               problem.doRawFitness(member[i]);

               sumRawFitness = sumRawFitness + member[i].rawFitness;
               sumRawFitness2 = sumRawFitness2 + member[i].rawFitness * member[i].rawFitness;

               if (Parameters.minORmax.equals("max"))
               {
                  if (member[i].rawFitness > bestOfGenChromo.rawFitness)
                  {
                     bestOfGenChromo.setEqual(member[i]);
                     bestOfGenR = R;
                     bestOfGenG = G;
                  }
                  if (member[i].rawFitness > bestOfRunChromo.rawFitness)
                  {
                     bestOfRunChromo.setEqual(member[i]);
                     bestOfRunR = R;
                     bestOfRunG = G;
                  }
                  for (int j = 0; j < BEST_CHROMO_COUNT; j++) // GWM - For loop added to check the entire array
                  {
                     if (member[i].rawFitness > bestOverAllChromo[j].rawFitness)
                     {
                        bestOverAllChromo[j].setEqual(member[i]);
                        bestOverAllR = R;
                        bestOverAllG = G;
                        break;
                     }
                  }
               } else
               {
                  if (member[i].rawFitness < bestOfGenChromo.rawFitness)
                  {
                     bestOfGenChromo.setEqual(member[i]);
                     bestOfGenR = R;
                     bestOfGenG = G;
                  }
                  if (member[i].rawFitness < bestOfRunChromo.rawFitness)
                  {
                     bestOfRunChromo.setEqual(member[i]);
                     bestOfRunR = R;
                     bestOfRunG = G;
                  }
                  for (int j = 0; j < BEST_CHROMO_COUNT; j++) // GWM - For loop added to check the entire array
                  {
                     if (member[i].rawFitness < bestOverAllChromo[j].rawFitness)
                     {
                        bestOverAllChromo[j].setEqual(member[i]);
                        bestOverAllR = R;
                        bestOverAllG = G;
                        break;
                     }
                  }
               }
            }

            // Accumulate fitness statistics
            fitnessStats[0][G] += sumRawFitness / Parameters.popSize;
            fitnessStats[1][G] += bestOfGenChromo.rawFitness;

            // CR - sum the square of the average and best for the generation
            fitnessStats[2][G] += (sumRawFitness / Parameters.popSize) * (sumRawFitness / Parameters.popSize);
            fitnessStats[3][G] += bestOfGenChromo.rawFitness * bestOfGenChromo.rawFitness;

            averageRawFitness = sumRawFitness / Parameters.popSize;
            stdevRawFitness = Math.sqrt(
                    Math.abs(sumRawFitness2
                    - sumRawFitness * sumRawFitness / Parameters.popSize)
                    / (Parameters.popSize - 1));

            // Output generation statistics to summary file
            Hwrite.right(R, 3, summaryOutput);
            summaryOutput.write(",");
            Hwrite.right(G, 4, summaryOutput);
            summaryOutput.write(",");
            Hwrite.right(bestOfGenChromo.rawFitness, 25, 5, summaryOutput);
            summaryOutput.write(",");
            Hwrite.right(averageRawFitness, 25, 5, summaryOutput);
            summaryOutput.write(",");
            Hwrite.right(stdevRawFitness, 25, 5, summaryOutput);

            //Output Best Chromo Simulation Statistics
            PrintSumoStatsRowForm(summaryOutput, bestOfGenChromo);


            summaryOutput.write("\n");

            // *********************************************************************
            // **************** SCALE FITNESS OF EACH MEMBER AND SUM ***************
            // *********************************************************************

            switch (Parameters.scaleType)
            {

               case 0:     // No change to raw fitness
                  for (int i = 0; i < Parameters.popSize; i++)
                  {
                     member[i].sclFitness = member[i].rawFitness + .000001;
                     sumSclFitness += member[i].sclFitness;
                  }
                  break;

               case 1:     // Fitness not scaled.  Only inverted.
                  for (int i = 0; i < Parameters.popSize; i++)
                  {
                     member[i].sclFitness = 1 / (member[i].rawFitness + .000001);
                     sumSclFitness += member[i].sclFitness;
                  }
                  break;

               case 2:     // Fitness scaled by Rank (Maximizing fitness)

                  //  Copy genetic data to temp array
                  for (int i = 0; i < Parameters.popSize; i++)
                  {
                     memberIndex[i] = i;
                     memberFitness[i] = member[i].rawFitness;
                  }
                  //  Bubble Sort the array by floating point number
                  for (int i = Parameters.popSize - 1; i > 0; i--)
                  {
                     for (int j = 0; j < i; j++)
                     {
                        if (memberFitness[j] > memberFitness[j + 1])
                        {
                           TmemberIndex = memberIndex[j];
                           TmemberFitness = memberFitness[j];
                           memberIndex[j] = memberIndex[j + 1];
                           memberFitness[j] = memberFitness[j + 1];
                           memberIndex[j + 1] = TmemberIndex;
                           memberFitness[j + 1] = TmemberFitness;
                        }
                     }
                  }
                  //  Copy ordered array to scale fitness fields
                  for (int i = 0; i < Parameters.popSize; i++)
                  {
                     member[memberIndex[i]].sclFitness = i;
                     sumSclFitness += member[memberIndex[i]].sclFitness;
                  }

                  break;

               case 3:     // Fitness scaled by Rank (minimizing fitness)

                  //  Copy genetic data to temp array
                  for (int i = 0; i < Parameters.popSize; i++)
                  {
                     memberIndex[i] = i;
                     memberFitness[i] = member[i].rawFitness;
                  }
                  //  Bubble Sort the array by floating point number
                  for (int i = 1; i < Parameters.popSize; i++)
                  {
                     for (int j = (Parameters.popSize - 1); j >= i; j--)
                     {
                        if (memberFitness[j - i] < memberFitness[j])
                        {
                           TmemberIndex = memberIndex[j - 1];
                           TmemberFitness = memberFitness[j - 1];
                           memberIndex[j - 1] = memberIndex[j];
                           memberFitness[j - 1] = memberFitness[j];
                           memberIndex[j] = TmemberIndex;
                           memberFitness[j] = TmemberFitness;
                        }
                     }
                  }
                  //  Copy array order to scale fitness fields
                  for (int i = 0; i < Parameters.popSize; i++)
                  {
                     member[memberIndex[i]].sclFitness = i;
                     sumSclFitness += member[memberIndex[i]].sclFitness;
                  }

                  break;

               default:
                  System.out.println("ERROR - No scaling method selected");
            }


            // *********************************************************************
            // ****** PROPORTIONALIZE SCALED FITNESS FOR EACH MEMBER AND SUM *******
            // *********************************************************************

            for (int i = 0; i < Parameters.popSize; i++)
            {
               member[i].proFitness = member[i].sclFitness / sumSclFitness;
               sumProFitness = sumProFitness + member[i].proFitness;
            }

            // *********************************************************************
            // ************ CROSSOVER AND CREATE NEXT GENERATION *******************
            // *********************************************************************

            int parent1 = -1;
            int parent2 = -1;

            //  Assumes always two offspring per mating
            for (int i = 0; i < Parameters.popSize; i = i + 2)
            {

               //	Select Two Parents
               parent1 = Chromo.selectParent(member);
               parent2 = parent1;
               while (parent2 == parent1)
               {
                  parent2 = Chromo.selectParent(member);
               }

               //	Crossover Two Parents to Create Two Children
               randnum = r.nextDouble();
               if (randnum < Parameters.xoverRate)
               {
                  member[parent1].mateParents(parent1, parent2, member[parent2], child[i], child[i + 1]);
               } else
               {
                  member[parent1].mateParents(parent1, child[i]);
                  member[parent2].mateParents(parent2, child[i + 1]);
               }
            } // End Crossover

            //	Mutate Children
            for (int i = 0; i < Parameters.popSize; i++)
            {
               child[i].doMutation();
            }

            //run random immigrants every 5 turns
            //RandomImmigrants.performRandomImmigrants(child);

            // If we have elitism, remove a child and replace with the best member from this generation
            if (Parameters.elitismType != 0)
            {
               child[0].setEqual(bestOfGenChromo);
            }
            
            //System.out.println(bestOfGenChromo.rawFitness);

            //	Swap Children with Last Generation
            for (int i = 0; i < Parameters.popSize; i++)
            {
               member[i].setEqual(child[i]);
            }
            

         } //  Repeat the above loop for each generation

         summaryOutput.write("Best Of Run,Best Of Generation,Chromo Value (Raw), Chromo Value(int), Raw Fitness,");
         PrintSumoStatHeaders(summaryOutput);

         Hwrite.left(bestOfRunR, 4, summaryOutput);
         summaryOutput.write(",");
         Hwrite.right(bestOfRunG, 4, summaryOutput);
         summaryOutput.write(",");

         problem.doPrintGenes(bestOfRunChromo, summaryOutput);
         PrintSumoStatsRowForm(summaryOutput, bestOfRunChromo);
         summaryOutput.write("\n\n\n");

         // collecting the runs best value
         bestOfRunsRawFitness[R - 1] = bestOfRunChromo.rawFitness;
      } //End of a Run

      summaryOutput.write("\n\nBest Chromosome\n");
      summaryOutput.write("#,Chromo Value(Raw), Chromo Value (int), Raw Fitness,");
      PrintSumoStatHeaders(summaryOutput);
      //summaryOutput.write("\n");
      summaryOutput.write("B,");
      problem.doPrintGenes(bestOverAllChromo[0], summaryOutput);
      PrintSumoStatsRowForm(summaryOutput, bestOverAllChromo[0]);
      summaryOutput.write("\n");

      //Use best chromosome found and output the traffic light program
      
      if (Parameters.problemType.equals("GA_TLP"))
      {
         new CreateXMLFile(bestOverAllChromo[0]);
      } else if (Parameters.problemType.equals("GA_TLP2"))
      {
         new CreateXMLFile2(bestOverAllChromo[0]);
      } else if (Parameters.problemType.equals("GA_TLP3"))
      {
         new CreateXMLFile3(bestOverAllChromo[0]);
      } else if (Parameters.problemType.equals("GA_TLP4"))
      {
          new CreateXMLFile(bestOverAllChromo[0]);
      } 
      else
      {
         System.out.println("Invalid Problem Type");
      }

      for (int j = 1; j < BEST_CHROMO_COUNT; j++) // GWM - Print all best chromos
      {
         summaryOutput.write(j + ",");
         Hwrite.left(" ", 8, summaryOutput);
         problem.doPrintGenes(bestOverAllChromo[j], summaryOutput);
         PrintSumoStatsRowForm(summaryOutput, bestOverAllChromo[j]);
         summaryOutput.write("\n");
      }

      // CR - output the average best over the runs and stdev
      double sums = 0;
      double sums2 = 0;
      for (int k = 0; k < Parameters.numRuns; k++)
      {
         sums += bestOfRunsRawFitness[k];
         sums2 += (bestOfRunsRawFitness[k] * bestOfRunsRawFitness[k]);
      }
      double avg = sums / Parameters.numRuns;
      double stdev = Math.sqrt(
              Math.abs(sums2
              - sums * sums / Parameters.numRuns)
              / (Parameters.numRuns - 1));
      summaryOutput.write("Average best-of-runs fitness," + avg);
      summaryOutput.write("\nBest-of-runs stdev," + stdev);

      //	Output Fitness Statistics matrix
      // CR - Output stdDev for AvgFit and BestFit
      summaryOutput.write("\n\nGen,AvgFit,BestFit,AvgStdev,BestStdev\n");

      for (int i = 0; i < Parameters.generations; i++)
      {
         // CR - Calculate stdevs before printing
         fitnessStats[2][i] = Math.sqrt(
                 Math.abs(fitnessStats[2][i]
                 - fitnessStats[0][i] * fitnessStats[0][i] / Parameters.numRuns)
                 / (Parameters.numRuns - 1));
         fitnessStats[3][i] = Math.sqrt(
                 Math.abs(fitnessStats[3][i]
                 - fitnessStats[1][i] * fitnessStats[1][i] / Parameters.numRuns)
                 / (Parameters.numRuns - 1));

         // Output
         Hwrite.left(i, 8, summaryOutput);
         summaryOutput.write(",");
         Hwrite.left(fitnessStats[0][i] / Parameters.numRuns, 15, 5, summaryOutput);
         summaryOutput.write(",");
         Hwrite.left(fitnessStats[1][i] / Parameters.numRuns, 15, 5, summaryOutput);
         summaryOutput.write(",");

         // CR - Added output for stdevs
         Hwrite.left(fitnessStats[2][i], 15, 5, summaryOutput);
         summaryOutput.write(",");
         Hwrite.left(fitnessStats[3][i], 15, 5, summaryOutput);
         summaryOutput.write("\n");
      }

      System.out.println();
      System.out.println("Start:  " + startTime);
      summaryOutput.write("\nStart," + startTime);
      dateAndTime = Calendar.getInstance();
      Date endTime = dateAndTime.getTime();
      System.out.println("End  :  " + endTime);
      summaryOutput.write("\nEnd," + endTime);

      summaryOutput.write("\n");
      summaryOutput.close();

      ///////////////////////////////////////////////////////////////////////////
      // Test output to print the population.
      //		popOutput.close();
      ///////////////////////////////////////////////////////////////////////////

   } // End of Main Class

   private static void PrintSumoStatHeaders(FileWriter output) throws java.io.IOException
   {
      if (Parameters.outputSumoStatsInFile == 1)
      {

         //Print Global Stats Headers
         output.write("Mean Waiting Time (All Lanes)" + ",");
         output.write("Mean Travel Time (All Lanes)" + ",");

         //Print rest of Headers
         for (int stats = 0; stats < 10; stats++)
         {
            String header = "";

            for (int lane = 0; lane < 12; lane++)
            {
               switch (lane)
               {
                  case 0:
                     header = "North Left Turn";
                     break;
                  case 1:
                     header = "North Forword";
                     break;
                  case 2:
                     header = "North Right Turn";
                     break;
                  case 3:
                     header = "East Left Turn";
                     break;
                  case 4:
                     header = "East Forward";
                     break;
                  case 5:
                     header = "East Right Turn";
                     break;
                  case 6:
                     header = "South Left Turn";
                     break;
                  case 7:
                     header = "South Forward";
                     break;
                  case 8:
                     header = "South Right Turn";
                     break;
                  case 9:
                     header = "West Left Turn";
                     break;
                  case 10:
                     header = "West Forward";
                     break;
                  case 11:
                     header = "West Right Turn";
                     break;
                  default:
                     System.out.println("No more lanes headers to print");
               }//switch


               //Append Statistics Heading
               switch (stats)
               {
                  case 0:
                     header += " Mean Travel Time";
                     break;
                  case 1:
                     header += " Mean Density";
                     break;
                  case 2:
                     header += " Mean Occupancy";
                     break;
                  case 3:
                     header += " Mean Waiting Time";
                     break;
                  case 4:
                     header += " Mean Speed";
                     break;
                  case 5:
                     header += " Vehicles Entered";
                     break;
                  case 6:
                     header += " Vehicles Left";
                     break;
                  case 7:
                     header += " Average Number of Vehicles";
                     break;
                  case 8:
                     header += " Average Traffic Volume (Cars/Hr)";
                     break;
                  case 9:
                     header += " Average Traffic Volume at Exit (Cars/Hr)";
                     break;
                  default:
                     System.out.println("No more stats headers to print");
               }//end case

               output.write(header + ",");
            }//end for lane
         }//end for stats

         output.write("\n");
      }

   }

   private static void PrintSumoStatsRowForm(FileWriter output, Chromo best) throws java.io.IOException
   {
      if (Parameters.outputSumoStatsInFile == 1)
      {
         output.write("," + best.meanWaitingTimeAllLanes + ",");
         output.write(best.meanTravelTimeAllLanes + ",");

         for (int i = 0; i < 12; i++)
         {
            output.write(best.meanTravelTime[constant.LaneNumberIndex(i)] + ",");
         }
         for (int i = 0; i < 12; i++)
         {
            output.write(best.meanDensity[constant.LaneNumberIndex(i)] + ",");
         }
         for (int i = 0; i < 12; i++)
         {
            output.write(best.meanOccupancy[constant.LaneNumberIndex(i)] + ",");
         }
         for (int i = 0; i < 12; i++)
         {
            output.write(best.meanWaitingTime[constant.LaneNumberIndex(i)] + ",");
         }
         for (int i = 0; i < 12; i++)
         {
            output.write(best.meanSpeed[constant.LaneNumberIndex(i)] + ",");
         }
         for (int i = 0; i < 12; i++)
         {
            output.write(best.vehiclesEntered[constant.LaneNumberIndex(i)] + ",");
         }
         for (int i = 0; i < 12; i++)
         {
            output.write(best.vehiclesLeft[constant.LaneNumberIndex(i)] + ",");
         }
         for (int i = 0; i < 12; i++)
         {
            output.write(best.meanNumberOfVehicles[constant.LaneNumberIndex(i)] + ",");
         }
         for (int i = 0; i < 12; i++)
         {
            output.write(best.meanTrafficVolumeCarsPerHour[constant.LaneNumberIndex(i)] + ",");
         }
         for (int i = 0; i < 12; i++)
         {
            output.write(best.meanTrafficVolumeAtExitCarsPerHour[constant.LaneNumberIndex(i)] + ",");
         }
      }

   }
}   // End of Search.Java ******************************************************

